package map;


public class LinkedListMap<K,V> implements Map<K,V> {

    private class Node{
        K key;
        V value;
        Node next;

        @Override
        public String toString() {
            return "key:"+key+",value:"+value;
        }

        public Node(){
            this(null,null,null);
        }

        public Node(K key,V value){
           this(key,value,null);
        }

        public Node(K key,V value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap(){
        dummyHead = new Node();
        size = 0;
    }

    @Override
    public void add(K key, V value) {
        //查看是否已经存在节点
        Node node = getNode(key);
        if (node != null) {
            //节点存在，并且添加的值与原本的值不等，更新操作
            if (!value.equals(node.value)) {
                node.value = value;
            }
        }else{
            //节点不存在，进行新增操作
            addNode(dummyHead,key, value);
        }
    }

    private Node addNode(Node node,K key,V value){
        if (node == null) {
            size++;
            return new Node(key,value);
        }
        node.next = addNode(node.next,key,value);
        return node;
    }

    @Override
    public V remove(K key) {
        //查找前一个节点
        Node prevNode = getPrevNode(key);
        if (prevNode != null) {
            Node cur = prevNode.next;
            prevNode.next = cur.next;
            V value = cur.value;
            cur = null;
            size--;
            return value;
        }
       throw new RuntimeException("元素不存在");
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null?true:false;
    }

    @Override
    public V get(K key) {
        Node cur = null;
        for(cur = dummyHead.next; cur != null;cur = cur.next){
            if (key.equals(cur.key)) {
                return cur.value;
            }
        }
        return null;
    }

    public Node getNode(K key) {
        Node cur = null;
        for(cur = dummyHead.next; cur != null;cur = cur.next){
            if (key.equals(cur.key)) {
                return cur;
            }
        }
        return null;
    }

    public Node getPrevNode(K key) {
        Node prev = null;
        for(prev = dummyHead; prev != null;prev = prev.next){
            if (key.equals(prev.next.key)) {
                return prev;
            }
        }
        return null;
    }



    @Override
    public void set(K key, V value) {
        //查看是否已经存在节点
        Node node = getNode(key);
        if (node != null) {
            //节点存在，并且添加的值与原本的值不等，更新操作
            if (!value.equals(node.value)) {
                node.value = value;
            }
        } else
            throw new RuntimeException("元素不存在");
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for(Node cur = dummyHead.next; cur!=null; cur=cur.next)
            sb.append(cur + "->");

        sb.append("NULL");
        return sb.toString();
    }

    public static void main(String[] args) {
        LinkedListMap map = new LinkedListMap<String,Integer>();
        for (int i = 0; i < 10; i++) {
            map.add("第"+i,i);
        }
        System.out.println(map);
        System.out.println("当前size大小为:"+map.size);
        System.out.println("是否包含第2个元素:"+map.contains("第2"));
        System.out.println("获取第2个元素:"+map.get("第2"));
        map.set("第2",100);
        System.out.println("set改变第2个元素:"+map.get("第2"));
        System.out.println(map);
        map.add("第2",500);
        System.out.println("add改变第2个元素:"+map.get("第2"));
        System.out.println(map);
        System.out.println("remove改变第2个元素:"+map.get("第2"));
        map.remove("第2");
        System.out.println(map);
    }
}
